<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,200分)- 贪吃蛇（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>贪吃蛇是一个经典游戏&#xff0c;蛇的身体由若干方格连接而成&#xff0c;身体随蛇头移动。蛇头触碰到食物时&#xff0c;蛇的长度会增加一格。蛇头和身体的任一方格或者游戏版图边界碰撞时&#xff0c;游戏结束。</p> 
<p>下面让我们来完成贪吃蛇游戏的模拟。</p> 
<p>给定一个N*M的数组arr&#xff0c;代表N*M个方格组成的版图&#xff0c;贪吃蛇每次移动一个方格。</p> 
<p>若arr[i][j] &#61;&#61; ‘H’&#xff0c;表示该方格为贪吃蛇的起始位置&#xff1b;</p> 
<p>若arr[i][j] &#61;&#61; ‘F’&#xff0c;表示该方格为食物&#xff0c;</p> 
<p>若arr[i][j] &#61;&#61; ‘E’&#xff0c;表示该方格为空格。</p> 
<p>贪吃蛇初始长度为1&#xff0c;初始移动方向为向左。</p> 
<p>为给定一系列贪吃蛇的移动操作&#xff0c;返回操作后蛇的长度&#xff0c;如果在操作执行完之前已经游戏结束&#xff0c;返回游戏结束时蛇的长度。</p> 
<p>贪吃蛇移动、吃食物和碰撞处理的细节见下面图示&#xff1a;</p> 
<p><img alt="" height="504" src="https://img-blog.csdnimg.cn/26bdc5c3c52a4e559f519d5282eab151.png" width="982" /></p> 
<p>图1&#xff1a;截取了贪吃蛇移动的一个中间状态&#xff0c;H表示蛇头&#xff0c;F表示食物&#xff0c;数字为蛇身体各节的编号&#xff0c;蛇为向左移动&#xff0c;此时蛇头和食物已经相邻</p> 
<p>图2&#xff1a;蛇头向左移动一格&#xff0c;蛇头和食物重叠&#xff0c;注意此时食物的格子成为了新的蛇头&#xff0c;第1节身体移动到蛇头位置&#xff0c;第2节身体移动到第1节身体位置&#xff0c;以此类推&#xff0c;最后添加第4节身体到原来第3节身体的位置。</p> 
<p>图3&#xff1a;蛇头继续向左移动一格&#xff0c;身体的各节按上述规则移动&#xff0c;此时蛇头已经和边界相邻&#xff0c;但还未碰撞。</p> 
<p>图4&#xff1a;蛇头继续向左移动一格&#xff0c;此时蛇头已经超过边界&#xff0c;发生碰撞&#xff0c;游戏结束。</p> 
<p>图5和图6给出一个蛇头和身体碰撞的例子&#xff0c;蛇为向上移动。</p> 
<p>图5时蛇头和第7节身体相邻&#xff0c;但还未碰撞&#xff1b;</p> 
<p>图6蛇头向上移动一格&#xff0c;此时蛇头和第8节身体都移动到了原来第7节身体的位置&#xff0c;发生碰撞&#xff0c;游戏结束。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入第一行为空格分隔的字母&#xff0c;代表贪吃蛇的移动操作。</p> 
<p>字母取值为U、D、L、R和G&#xff0c;</p> 
<p>U、D、L、R分别表示贪吃蛇往上、下、左、右和转向&#xff0c;转向时贪吃蛇不移动 &#xff0c;G表示贪吃蛇按当前的方向移动一格。</p> 
<p>用例保证输入的操作正确。</p> 
<p>第二行为空格分隔的两个数&#xff0c;指定N和M&#xff0c;为数组的行和列数。</p> 
<p>余下N行每行是空格分隔的M个字母。字母取值为H、F和E&#xff0c;H表示贪吃蛇的起始位置&#xff0c;F表示食物&#xff0c;E表示该方格为空。</p> 
<p>用例保证有且只有一个H&#xff0c;而F和E会有多个。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出一个数字&#xff0c;为蛇的长度。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">D G G<br /> 3 3<br /> F F F<br /> F F H<br /> E F E</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">1</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>地图表示为&#xff1a;</p> 
    <ul><li>蛇头 H(Head)</li><li>食物 F(Food)</li><li>E表示该方格为空</li></ul><p></p> <p>四个方向分别表示为&#xff1a;</p> 
    <ul><li>向上 U(up)</li><li>向下 D(down)</li><li>向左 L(Left)</li><li>向右 R(Right)</li></ul></td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>纯逻辑题。</p> 
<p>本题难点在于当贪吃蛇移动后&#xff0c;更新贪吃蛇的位置&#xff0c;以及矩阵各坐标的信息的逻辑。</p> 
<p>首先&#xff0c;我使用一个数组snake来维护贪吃蛇的位置&#xff0c;蛇头就是snake[0]。</p> 
<p>当贪吃蛇移动时&#xff0c;如果蛇头去往的位置是空地&#xff0c;即matrix[i][j] &#61; &#39;E&#39;的话&#xff0c;则</p> 
<pre><code class="language-javascript">snake.unshift([i,j])
let [aI, aJ] &#61; snake.pop() // 由于去往的是空地&#xff0c;因此贪吃蛇不会生长&#xff0c;所以蛇尾的位置要pop出去
matrix[aI][aJ] &#61; &#39;E&#39; // 并且要更新pop出去的位置为空地
matrix[i][j] &#61; &#39;H&#39; // 而蛇头达到的新位置要更新为蛇头位置H</code></pre> 
<p>当贪吃蛇移动时&#xff0c;如果蛇头去往的位置是食物&#xff0c;即matrix[i][j] &#61; &#39;F&#39;的话&#xff0c;则</p> 
<pre><code class="language-javascript">snake.unshift([i,j])
matrix[i][j] &#61; &#39;H&#39; // 更新蛇头位置</code></pre> 
<p>当贪吃蛇移动时&#xff0c;如果蛇头去往的位置是自己的身体&#xff0c;即matrix[i][j] &#61; &#39;H&#39;&#xff0c;</p> 
<blockquote> 
 <p>注意我这里并不需要根据‘H’来判断移动中蛇头的位置&#xff0c;而是总是用snake[0]作为蛇头&#xff0c;因此matrix[i][j] &#61; &#39;H&#39;可以直接用于标记贪吃蛇身体&#xff0c;来区别F、E。</p> 
</blockquote> 
<p>则&#xff0c;此时游戏结束&#xff0c;输出snake.length</p> 
<p>另外&#xff0c;当贪吃蛇移动的位置越界了&#xff0c;游戏也结束&#xff0c;输出snake.length</p> 
<p></p> 
<p>自测用例</p> 
<p><img alt="" height="216" src="https://img-blog.csdnimg.cn/391500258b8a4bb09e12d41143913d9c.png" width="1200" /></p> 
<blockquote> 
 <p>D G L G G U G G R G G D G L G<br /> 3 3<br /> F F F<br /> F F H<br /> E F E </p> 
</blockquote> 
<p>最终贪吃蛇的长度为7</p> 
<p></p> 
<p><img alt="" height="228" src="https://img-blog.csdnimg.cn/7dcc5c047c9b4aeeb4d3ea6d4382c06f.png" width="1200" /></p> 
<blockquote> 
 <p>D G L G U G R G U G L G D G<br /> 3 3<br /> F F F<br /> F F H<br /> E F E</p> 
</blockquote> 
<p>最终贪吃蛇的长度为5</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  const operates &#61; (await readline()).split(&#34; &#34;);
  const [n, m] &#61; (await readline()).split(&#34; &#34;).map(Number);

  const matrix &#61; [];
  for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
    matrix.push((await readline()).split(&#34; &#34;));
  }

  const snake &#61; [];
  const offset &#61; [0, -1]; // 蛇头移动初始向左

  for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
    for (let j &#61; 0; j &lt; m; j&#43;&#43;) {
      if (&#34;H&#34; &#61;&#61; matrix[i][j]) snake.push(new Pos(i, j)); // 找到初始蛇头位置&#xff0c;并使用snake[0]来维护蛇头位置
    }
  }

  for (let op of operates) {
    switch (op) {
      case &#34;U&#34;:
        offset[0] &#61; -1;
        offset[1] &#61; 0;
        break;
      case &#34;D&#34;:
        offset[0] &#61; 1;
        offset[1] &#61; 0;
        break;
      case &#34;L&#34;:
        offset[0] &#61; 0;
        offset[1] &#61; -1;
        break;
      case &#34;R&#34;:
        offset[0] &#61; 0;
        offset[1] &#61; 1;
        break;
      case &#34;G&#34;:
        const head &#61; snake[0];
        const head_next &#61; new Pos(head.x &#43; offset[0], head.y &#43; offset[1]);

        if (
          head_next.x &lt; 0 ||
          head_next.x &gt;&#61; n ||
          head_next.y &lt; 0 ||
          head_next.y &gt;&#61; m
        ) {
          return console.log(snake.length);
        }

        const tail &#61; snake.at(-1);

        switch (matrix[head_next.x][head_next.y]) {
          case &#34;E&#34;:
            // 如果蛇头去的地方是空地&#xff0c;则:
            // 蛇身的每个位置都递进为前面一个位置&#xff0c;蛇尾巴位置恢复为空地
            matrix[tail.x][tail.y] &#61; &#34;E&#34;;
            snake.pop();
            // 蛇头进入新位置
            matrix[head_next.x][head_next.y] &#61; &#34;H&#34;;
            snake.unshift(head_next);
            break;
          case &#34;F&#34;:
            // 如果蛇头去的地方是食物&#xff0c;则蛇身长度增加一&#xff0c;相当于蛇身各部分位置不变&#xff0c;蛇头变到当前去的位置
            matrix[head_next.x][head_next.y] &#61; &#34;H&#34;;
            snake.unshift(head_next);
            break;
          case &#34;H&#34;:
            if (head_next.eq(tail)) {
              // 如果蛇头去的地方是蛇尾&#xff0c;则由于递进关系&#xff0c;蛇头是吃不到蛇尾的
              snake.unshift(snake.pop());
            } else {
              // 如果蛇头去的地方是蛇身&#xff0c;则会吃到自己
              return console.log(snake.length);
            }
            break;
        }

        break;
    }
  }

  console.log(snake.length);
})();

class Pos {
  constructor(x, y) {
    this.x &#61; x;
    this.y &#61; y;
  }

  eq(pos) {
    return this.x &#61;&#61; pos.x &amp;&amp; this.y &#61;&#61; pos.y;
  }
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  // 坐标类
  static class Pos {
    int x;
    int y;

    public Pos(int x, int y) {
      this.x &#61; x;
      this.y &#61; y;
    }

    public boolean equals(Pos pos) {
      return this.x &#61;&#61; pos.x &amp;&amp; this.y &#61;&#61; pos.y;
    }
  }

  static String[] operates;
  static String[][] matrix;
  static int n;
  static int m;

  static LinkedList&lt;Pos&gt; snake &#61; new LinkedList&lt;&gt;();
  static int[] offset &#61; new int[] {0, -1}; // 蛇头移动初始向左

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    operates &#61; sc.nextLine().split(&#34; &#34;);

    int[] tmp &#61; Arrays.stream(sc.nextLine().split(&#34; &#34;)).mapToInt(Integer::parseInt).toArray();
    n &#61; tmp[0];
    m &#61; tmp[1];

    matrix &#61; new String[n][m];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      for (int j &#61; 0; j &lt; m; j&#43;&#43;) {
        matrix[i][j] &#61; sc.next();

        if (&#34;H&#34;.equals(matrix[i][j])) {
          snake.addLast(new Pos(i, j)); // 找到初始蛇头位置&#xff0c;并使用snake[0]来维护蛇头位置
        }
      }
    }

    System.out.println(getResult());
  }

  public static int getResult() {
    for (String operate : operates) {
      switch (operate) {
        case &#34;U&#34;:
          offset[0] &#61; -1;
          offset[1] &#61; 0;
          break;
        case &#34;D&#34;:
          offset[0] &#61; 1;
          offset[1] &#61; 0;
          break;
        case &#34;L&#34;:
          offset[0] &#61; 0;
          offset[1] &#61; -1;
          break;
        case &#34;R&#34;:
          offset[0] &#61; 0;
          offset[1] &#61; 1;
          break;
        case &#34;G&#34;:
          Pos head &#61; snake.getFirst();
          Pos head_next &#61; new Pos(head.x &#43; offset[0], head.y &#43; offset[1]);

          if (head_next.x &lt; 0 || head_next.x &gt;&#61; n || head_next.y &lt; 0 || head_next.y &gt;&#61; m) {
            return snake.size();
          }

          Pos tail &#61; snake.getLast();

          switch (matrix[head_next.x][head_next.y]) {
            case &#34;E&#34;:
              // 如果蛇头去的地方是空地&#xff0c;则:
              // 蛇身的每个位置都递进为前面一个位置&#xff0c;蛇尾巴位置恢复为空地
              matrix[tail.x][tail.y] &#61; &#34;E&#34;;
              snake.removeLast();
              // 蛇头进入新位置
              matrix[head_next.x][head_next.y] &#61; &#34;H&#34;;
              snake.addFirst(head_next);
              break;
            case &#34;F&#34;:
              // 如果蛇头去的地方是食物&#xff0c;则蛇身长度增加一&#xff0c;相当于蛇身各部分位置不变&#xff0c;蛇头变到当前去的位置
              matrix[head_next.x][head_next.y] &#61; &#34;H&#34;;
              snake.addFirst(head_next);
              break;
            case &#34;H&#34;:
              if (head_next.equals(tail)) {
                // 如果蛇头去的地方是蛇尾&#xff0c;则由于递进关系&#xff0c;蛇头是吃不到蛇尾的
                snake.addFirst(snake.removeLast());
              } else {
                // 如果蛇头去的地方是蛇身&#xff0c;则会吃到自己
                return snake.size();
              }
              break;
          }

          break;
      }
    }

    return snake.size();
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
operates &#61; input().split()
n, m &#61; map(int, input().split())
matrix &#61; [input().split() for _ in range(n)]

# 记录蛇各个部分位置
snake &#61; []
# 蛇头移动初始向左 [行偏移量&#xff0c;列偏移量]&#xff0c;向左即列位置-1
offset &#61; [0, -1]


# 坐标类
class Pos:
    def __init__(self, x, y):
        self.x &#61; x
        self.y &#61; y

    def __eq__(self, other):
        return self.x &#61;&#61; other.x and self.y &#61;&#61; other.y


# 算法入口
def getResult():
    # 找到初始蛇头位置&#xff0c;并使用snake[0]来维护蛇头位置
    for i in range(n):
        for j in range(m):
            if &#34;H&#34; &#61;&#61; matrix[i][j]:
                snake.append(Pos(i, j))

    for op in operates:
        if op &#61;&#61; &#34;U&#34;:
            offset[0] &#61; -1
            offset[1] &#61; 0
        elif op &#61;&#61; &#34;D&#34;:
            offset[0] &#61; 1
            offset[1] &#61; 0
        elif op &#61;&#61; &#34;L&#34;:
            offset[0] &#61; 0
            offset[1] &#61; -1
        elif op &#61;&#61; &#34;R&#34;:
            offset[0] &#61; 0
            offset[1] &#61; 1
        elif op &#61;&#61; &#34;G&#34;:
            head &#61; snake[0]
            head_next &#61; Pos(head.x &#43; offset[0], head.y &#43; offset[1])

            if head_next.x &lt; 0 or head_next.x &gt;&#61; n or head_next.y &lt; 0 or head_next.y &gt;&#61; m:
                return len(snake)

            tail &#61; snake[-1]

            cell &#61; matrix[head_next.x][head_next.y]
            if cell &#61;&#61; &#34;E&#34;:
                # 如果蛇头去的地方是空地&#xff0c;则:
                # 蛇身的每个位置都递进为前面一个位置&#xff0c;蛇尾巴位置恢复为空地
                matrix[tail.x][tail.y] &#61; &#34;E&#34;
                snake.pop()
                # 蛇头进入新位置
                matrix[head_next.x][head_next.y] &#61; &#34;H&#34;
                snake.insert(0, head_next)
            elif cell &#61;&#61; &#34;F&#34;:
                # 如果蛇头去的地方是食物&#xff0c;则蛇身长度增加一&#xff0c;相当于蛇身各部分位置不变&#xff0c;蛇头变到当前去的位置
                matrix[head_next.x][head_next.y] &#61; &#34;H&#34;
                snake.insert(0, head_next)
            elif cell &#61;&#61; &#34;H&#34;:
                # 如果蛇头去的地方是蛇尾&#xff0c;则由于递进关系&#xff0c;蛇头是吃不到蛇尾的
                if head_next &#61;&#61; tail:
                    snake.insert(0, snake.pop())
                else:
                    # 如果蛇头去的地方是蛇身&#xff0c;则会吃到自己
                    return len(snake)

    return len(snake)


# 算法调用
print(getResult())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>